This is the companion notebook to the introductory course on simple portfolio construction and performance metrics. It contains simple examples of portfolio backtesting. The structures of this section will be used later on in the course.

\(\rightarrow\) ABOUT THE NOTEBOOK:

  • the code chunks are sequential. They must be executed in the correct order.
  • text between stars appears in bold in html format.

1 A glimpse at the S&P500

The S&P500 is one of the most widely scrutinised index in the US Equity investment space. It serves very often as benchmark. The purpose of this section is to unveil a few of its statistical properties and to use the highcharter package for highchart rendering in R.

1.1 Prices

We start by loading the packages and downloading the data.

if(!require(highcharter)){install.packages("highcharter")} # Package for nice financial graphs
There were 22 warnings (use warnings() to see them)
library(tidyverse)
library(lubridate)
library(quantmod)    # The package that eases the downloading of financial data
library(highcharter) # The package for financial time-series plots
min_date <- "1995-01-01"
max_date <- "2019-02-12"
prices <- getSymbols("^GSPC", src = 'yahoo',  # Yahoo source (strange ticker)
             from = min_date, 
             to = max_date,
             auto.assign = TRUE, 
             warnings = FALSE) %>% 
  map(~Ad(get(.))) %>% 
  reduce(merge) %>%
  `colnames<-`("SP500")

Then, we turn to plotting, using highchart format. We underline that this package works with special xts (R extensible time-series) format. We point to the package reference for more details on this subject.

hc <- highchart(type = "stock") %>%
    hc_title(text = "Evolution of the S&P500") %>%
    hc_add_series(prices)
htmltools::tagList(hc)              # Used for html export

export_hc(hc, filename = "hc.js")   # Export

A nice feature of highcharts is that they allow the user to change the observation period and see the values of points on the curve.

1.2 Returns

Next, we turn to the distribution of returns.

returns <- (prices/lag(prices) - 1) %>% # Formula for returns
    data.frame(Date = index(.))     %>% # Adding the Date as a column
    na.omit()                           # Removing NA rows
m <- mean(returns$SP500)                # Average daily return
s <- sd(returns$SP500)                  # Volatility = sd of daily returns
returns %>% ggplot() +                  # Plot
    geom_histogram(aes(x = SP500, y = ..density..), bins = 100) +
    stat_function(fun = dnorm, args = list(mean = m, sd = s), aes(color = "Gaussian"))

We plot the Gaussian distribution with parameters corresponding to the sample mean and standard deviation. Small grey rectangles around \(\pm 0.05\) indicate that large positive and negative returns occur more often than estimate by the Gaussian law: the tails of their distribution are notoriously heavy.

1.3 Volatility

Finally, we take a dynamic look at the volatility. We take a frugal approach; much more elegant methods are presented in Section 4.5 of Reproducible Finance by Jonathan Regenstein.

nb_days <- 63   # 63 days roughly equivalent to 3 months 
vol <- 0        # Initialisation
for(i in 1:(nrow(returns) - nb_days + 1)){          # Loop on dates: not elegant!
  vol[i] <- sd(returns$SP500[i:(i + nb_days - 1)])  # Vol computed on rolling window of nb_days
}
Date <- returns$Date[nb_days:nrow(returns)]
vol <- data.frame(vol*sqrt(252))
rownames(vol) <- Date
hc_vol <- highchart(type = "stock") %>%
    hc_title(text = "Evolution of volatility") %>%
    hc_add_series(as.xts(vol))
htmltools::tagList(hc_vol)              # Used for html export

Clearly the graph shows periods of low volatility and clusters of high market turbulence (crashes, most of the time). Returns are therefore not stationary. The properties we exhibited for the S&P500 are also true at the individual stock level.

In the next section, we turn to the core topic of portfolio backtesting.

2 A universe of functions

Backtesting portfolio strategies is usually simple at first, but becomes more intricate when many options are considered. To keep things simple, it is more efficient to work with functions. Functions help compartmentalise the different tasks of the process. We will build functions that compute portfolio weights and others that evaluate the performance metrics of the strategies. While we will usually work with a loop on backtesting dates, it is possible to build functions that directly generate portfolio returns (see below: the map() function).

But first, we start with the preprocessing of the data.

2.1 Data preparation

We first import and arrange the data. The data consists of monhtly financial information pertaining to 30 large US firms. They are characterised by their ticker symbol:

A - F G - M O - Z
AAPL (Apple) GE (General Electric) ORCL (Oracle)
BA (Boeing) HD (Home Depot) PFE (Pfizer)
BAC (Bank of America) IBM PG (Procter & Gamble)
C (Citigroup) INTC (Intel) T (AT&T)
CSCO (Cisco) JNJ (Johnson & Johnson) UNH (United Health)
CVS (CVS Health) JPM (JP Morgan) UPS
CVX (Chevron) K (Kellogg) VZ (Verizon)
D (Dominion Energy) MCK (McKesson) WFC (Wells Fargo)
DIS (Disney) MRK (Merck) WMT (Walmart)
F (Ford) MSFT (Microsoft) XOM (Exxon)

There are 7 attributes: closing price (Close), market capitalisation in M$ (Mkt_Cap), price-to-book ratio (P2B), 1 month volatility (Vol_1M), 1 month relative strength index (RSI_1M), debt-to-equity ratio (D2E) and profitability margin (Prof_Marg).
Finally, the time range is 2000-2018.

load("data.RData")                      # Loading the data: IF DIRECTORY OK!
data <- data %>% arrange(Date,Tick)     # Ranked first according to date and then stocks
summary(data)                           # Descriptive statistics
      Tick           Date                Close            Mkt_Cap            P2B           
 AAPL   : 221   Min.   :2000-01-03   Min.   :  1.004   Min.   :  4491   Min.   :   0.0922  
 BA     : 221   1st Qu.:2004-08-02   1st Qu.: 28.050   1st Qu.: 63498   1st Qu.:   2.0783  
 BAC    : 221   Median :2009-03-02   Median : 42.535   Median :128864   Median :   3.1054  
 C      : 221   Mean   :2009-03-02   Mean   : 57.519   Mean   :145819   Mean   :   6.6966  
 CSCO   : 221   3rd Qu.:2013-10-01   3rd Qu.: 66.045   3rd Qu.:198487   3rd Qu.:   5.2977  
 CVS    : 221   Max.   :2018-05-01   Max.   :557.000   Max.   :887952   Max.   :1259.1554  
 (Other):5304                                                                              
     Vol_1M            RSI_1M           D2E             Prof_Marg      
 Min.   :  5.276   Min.   :22.04   Min.   :    0.00   Min.   :-106.26  
 1st Qu.: 15.778   1st Qu.:46.12   1st Qu.:   29.36   1st Qu.:   5.11  
 Median : 21.607   Median :51.60   Median :   60.55   Median :  10.13  
 Mean   : 26.898   Mean   :51.64   Mean   :  191.92   Mean   :  11.70  
 3rd Qu.: 31.826   3rd Qu.:57.10   3rd Qu.:  205.02   3rd Qu.:  18.84  
 Max.   :265.429   Max.   :84.84   Max.   :14585.61   Max.   : 145.58  
                                                                       

This simple table shows a possible outlier for the P2B variable. The maximum value is clearly out of range.
Next, we format the data for future use. Notably, we compute returns.

data <- data  %>% 
    group_by(Tick) %>%                          # Grouping: returns computed stock-by-stock
    mutate(Return = Close / lag(Close) - 1) %>% # Adding returns
    na.omit()                                   # Take out missing values
returns <- data %>%                             # Take data
    select(Tick, Date, Return) %>%              # Select 3 columns
    spread(key = Tick, value = Return)          # Put them into 'matrix' format
returns                                         # Show the returns

By definition, a portfolio is a choice of weights that sum to one. Below, we implement two classical weighting schemes: the uniform portfolio (EW = equal weights) and the maximum Sharpe ratio portfolio (MSR). The latter is more complicated and requires inputs: namely the column vector of (expected) mean \(\mu\) and covariance matrix \(\Sigma\) of the assets. For simplicity, we will estimate them using sample moments - even though this is known to be a bad choice. This requires an additional argument in the function: the assets’ past returns. The MSR weights are \(w=\frac{\Sigma^{-1}\mu}{1'\Sigma^{-1}\mu}\). Both \(\mu\) and 1 are vectors here.

weights_msr <- function(returns){ # returns will refer to PAST returns
    m <- apply(returns, 2, mean)  # Vector of average returns
    sigma <- cov(returns)         # Covariance matrix
    w <- solve(sigma) %*% m       # Raw weights
    return(w / sum(w))            # Returns normalised weights
}
weights_ew <- function(returns){  # We keep the same syntax for simplicity
    N <- length(returns[1,])      # Number of assets
    return(rep(1/N,N))            # Weight = 1/N
}

We are now ready to proceed with the initialisation of the variables that will use in the main loop.

tick <- levels(data$Tick)               # Set of assets
t_all <- unique(data$Date)              # Set of dates
sep_date <- as.Date("2010-01-01")       # This date separates in-sample vs out-of-sample
t_oos <- t_all[t_all > sep_date]        # Out-of-sample dates (i.e., testing set)
portf_weights <- matrix(0, nrow = length(t_oos), # Will store portfolio weights
                           ncol = length(tick)) 
portf_returns <- c()                    # Will store portfolio returns

2.2 A first example

At last, we can proceed to the main loop. A note of caution: both in the weighting scheme functions and in the loop below, we assume well defined (finite, i.e., non NA) data. Obviously, feeding NA data in the system will produce NA outputs. There are only four steps in the loop:

  1. extract the data
  2. compute portfolio weights
  3. compute realised returns
  4. derive the return of the portfolio
for(t in 1:length(t_oos)){
    temp_data <- returns %>% filter(Date < t_oos[t]) # 1) Extracting past data: expanding window! 
    portf_weights[t,] <- temp_data %>%               # 2) Take this past data 
        select(-Date) %>%                            # Take out the date column
        weights_msr()                                # Appply the weighting scheme function
    realised_returns <- returns %>%                  # 3) Take returns
        filter(Date ==  t_oos[t]) %>%                # Keep only current date
        select(-Date)                                # Take out the date column
    portf_returns[t] <- sum(portf_weights[t,] * realised_returns) # 4) Compute the return
}

In the above backtest, the amount of data considered to form the portfolio decision increases with time (expanding window). It is easy to fix the number of data point at each step and proceed on rolling windows (exercise). Likewise, switching from MSR to EW is immediate (just change the weighting function).

The main output is the vector of portfolio returns. We can easily plot the evolution of the portfolio through time.

port <- data.frame(t_oos, cumprod(1+portf_returns))         # Portf. values via cumulative product
colnames(port) <- c("Date", "Portfolio")                    # Changing column names
port %>% ggplot() + geom_line(aes(x = Date, y = Portfolio)) # Plot

Below, we create a function that takes a series of returns as input and provides a few simple performance metrics.

perf_met <- function(returns){
    avg_ret <- mean(returns, na.rm = T)                     # Arithmetic mean 
    vol <- sd(returns, na.rm = T)                           # Volatility
    Sharpe_ratio <- avg_ret / vol                           # Sharpe ratio
    VaR_5 <- quantile(returns, 0.05)                        # Value-at-risk
    met <- data.frame(avg_ret, vol, Sharpe_ratio, VaR_5)    # Aggregation of all of this
    rownames(met) <- "metrics"
    return(met)
}
perf_met(portf_returns) # Let's test on the actual returns

Note: the values are not annualised. The annualisation can be directly coded into the function. A heuristic way to proceed is to multiply average returns by 12 and volatilities by \(\sqrt{12}\) - though this omits the compounding effect. These simplifications are ok if they are used to compare strategies. The Value at Risk is nontheless dependent on the return horizon and cannot be proxied so simply.

An important indicator is the turnover of the portfolio: it assesses asset rotation and thus impacts transaction costs. Simple turnover computes average absolute variation in portfolio weights: \(\text{Turn}=\frac{1}{T}\sum_{t=2}^T\sum_{n=1}^N|w_t^n-w_{t-1}^n|\). Full turnover takes into account the variation of the weights between rebalancing dates: \(\text{Turn}=\frac{1}{T}\sum_{t=2}^T\sum_{n=1}^N|w_t^n-w_{t-}^n|\), where \(t-\) is the time just before the rebalancing date.

turnover_simple <- function(weights){
    turn <- 0
    for(t in 2:length(t_oos)){
          turn <- turn + sum(abs(weights[t,] - weights[t-1,])) # Variation in weights
    }
    return(turn/(length(t_oos)-1))  # BEWARE: monthly value!
}
turnover_simple(portf_weights)      # Simple turnover!
[1] 0.3035889

Below, we switch to the full definition of the turnover. In this case, the variation in weights is adjusted because the weight prior to rebalancing have drifted.

turnover_full <- function(weights, asset_returns, t_oos){
    turn <- 0
    for(t in 2:length(t_oos)){
        realised_returns <- returns %>% filter(Date == t_oos[t]) %>% select(-Date)
        prior_weights <- weights[t-1,] * (1 + realised_returns) # Before rebalancing
        turn <- turn + apply(abs(weights[t,] - prior_weights/sum(prior_weights)),1,sum)
    }
    return(turn/(length(t_oos)-1))
}
asset_returns <- returns %>% filter(Date > sep_date)    # Asset returns over the experiment
turnover_full(portf_weights, asset_returns, t_oos)      # Real turnover
[1] 0.3989153

Note that the turnover is computed at the monthly frequency. The second value is always more realistic; in this case it is substantially higher compared to the simplified proxy. For the sake of compactness, the turnover should be included in the perf_met() function.

3 Extensions

3.1 Comparing strategies

An important generalisation of the above framework is to consider more than one strategy. Comparisons are commonplace in the asset management industry: obviously, people look for the best strategy (according to particular goals, beliefs, and preferences). Below, we show how this can be handled. We will compare the two strategies that we mentionned above. First, we need to re-initiate the variables because their dimension will change (NOTE: an alternative route would be to work with lists).

Tt <- length(t_oos)                                             # Nb of computation dates 
# Avoid T because T = TRUE!
nb_port <- 2                                                    # Nb of portfolios
portf_weights <- array(0, dim = c(Tt, nb_port, length(tick)))   # Store weights
portf_returns <- matrix(0, nrow = Tt, ncol = nb_port)           # Store returns

Second, we embed all weighting schemes into one single function.

weights_multi <- function(returns,j){   # Strategies are indexed by j
    if(j == 1){ # j = 1 => MSR
        return(weights_msr(returns))
    }
    if(j == 2){ # j = 2 => EW
        N <- length(returns[1,])
        return(rep(1/N,N))
    }
}

We decided to recode the EW strategy, but we could have used the weights_ew() function instead. Finally, the main loop is only marginally different from the single strategy loop.

for(t in 1:length(t_oos)){
    temp_data <- returns %>% 
        filter(Date < t_oos[t]) %>% 
        select(-Date)
    for(j in 1:nb_port){                           # This is the novelty: we loop on the strategies 
        portf_weights[t,j,] <- weights_multi(temp_data, j)  # The weights' function is indexed by j
        realised_returns <- returns %>% 
            filter(Date ==  t_oos[t]) %>% 
            select(-Date)
        portf_returns[t,j] <- sum(portf_weights[t,j,] * realised_returns)
    }
}
apply(portf_returns,2,perf_met) %>%                     # Taking perf metrics
    unlist() %>%                                        # Flattening the list
    matrix(nrow = 2, byrow = T) %>%                     # Ordering them
    `colnames<-`(c("avg_ret", "vol", "SR", "VaR")) %>%  # Adding column names
    data.frame()                                        # Converting to dataframe
apply(portf_weights, 2, turnover_simple) %>% unlist()
[1] 0.3035889 0.0000000

We recall the order of strategies: MSR first (line) and EW second (line).

Again, turnover should (and will) be added to the performance metric function. Since uniform weights are constant, their simplified turnover is zero. In practice, that is not the case because weights evolve according to asset returns. The adjustment would imply only a small turnover.

There is a well-documented substantial difference between the two weigting schemes in terms of asset rotation. The MSR that we compute is clearly not competitive: even before transaction costs, its Sharpe ratio is smaller than that of the EW portfolio (see DeMiguel et al. (2009) for further evidence on the robustness of the EW portfolio).

3.2 Make do without loops

Finally, we show how to bypass the loop over dates. While this is not useful on small datasets, it can save time on large databases because loops are notoriously time-consuming. Below, we show how to proceed with the map() function in the simple case with only one strategy.

# We create a function that will compute returns for each date:
port_map <- function(t_oos, returns){             
    temp_data <- returns %>% filter(Date < t_oos) # Still expanding window...
    portf_weights <- temp_data %>% 
        select(-Date) %>% 
        weights_msr()
    realised_returns <- returns %>% 
        filter(Date ==  t_oos) %>% 
        select(-Date)
    return(sum(portf_weights * realised_returns))
}
# the map() function does it all!
portf_returns <- t_oos %>%                      # The variable over which we loop
    map(~port_map(.x, returns = returns)) %>%   # Is sent to the map() function
    unlist()                                    # The output is flattened
perf_met(portf_returns)                         # Compute the perf metrics

4 Characteristics-based choice

In this section, we start the chapter of strategies based on firm characteristics (features). As an illustration, we check a well-documented (though still controversial) anomaly: the size effect. We build two portfolios: in the first (resp. second) one, we invest in the firms that have a below (resp. above) median market capitalisation. The first portfolio will be a ‘small’ portfolio and the second one a ‘large’ one. Stocks are equally-weighted inside the portfolios.

First, we prepare the variables and define the weight function.

nb_port <- 2                                                      # Nb of portfolios
portf_weights <- array(0, dim = c(Tt-1, nb_port, length(tick)))   # Where we store weights
portf_returns <- matrix(0, nrow = Tt-1, ncol = nb_port)           # Where we store returns
weights_cap <- function(data,j){    
# More general than before: we feed all the data, not just returns
    m <- median(data$Mkt_Cap)       # Compute the median market cap
    n <- nrow(data)                 # Compute the number of assets
    if(j == 1){return((data$Mkt_Cap < m)/n*2)} # Small cap
    if(j == 2){return((data$Mkt_Cap > m)/n*2)} # Large cap
}

There will only be Tt-1 dates since we lose one because of the computation of future returns.

Second, we can launch the backtesting loop.

for(t in 2:length(t_oos)){
    temp_data <- data %>% filter(Date == t_oos[t-1])        # We keep the data of the previous date
    for(j in 1:nb_port){                                    # We loop on the strategies 
        portf_weights[t-1,j,] <- weights_cap(temp_data, j)  # The weights' function is indexed by j
        realised_returns <- returns %>% 
            filter(Date ==  t_oos[t]) %>% 
            select(-Date)
        portf_returns[t-1,j] <- sum(portf_weights[t-1,j,] * realised_returns)
    }
}

Third, we proceed to performance metrics.

apply(portf_returns,2,perf_met) %>%                     # Taking perf metrics
    unlist() %>%                                        # Flattening the list
    matrix(nrow = 2, byrow = T) %>%                     # Ordering them
    `colnames<-`(c("avg_ret", "vol", "SR", "VaR")) %>%  # Adding column names
    data.frame()                                        # Converting to dataframe

Small firms do indeed generate a higher level of performance! In order to reach this conclusion in a rigourous fashion, we would need to perform the same analysis on at least 1,000 stocks (ideally, more) and on 5 to 10 portfolio sorts (from very small firms to very large ones). Below, we check the weights of the portfolio on one particular date.

small <- portf_weights[2,1,] # t = 2, j = 1 (t_oos[2] = 2010-03-01, small firms)
large <- portf_weights[2,2,] # t = 2, j = 2 (t_oos[2] = 2010-03-01, large firms)
data.frame(small, large, row.names = tick)

Indeed, some stocks have zero weights and others 1/15.

Finally, let’s see how we could have coded those strategies using the tidyverse (and a lot of piping!).

data %>% filter(Date > sep_date) %>%            # Keep only the out-of-sample backtesting dates
    group_by(Tick) %>%                          # Group by stock
    mutate(F_Return = lead(Return)) %>%         # Compute forward (i.e., realised) return
    na.omit() %>%                               # Take out NAs
    group_by(Date) %>%                          # Group by dates
    mutate(Mkt_Cap_Binary = Mkt_Cap < median(Mkt_Cap)) %>%  # Compute median cap for each date
    group_by(Mkt_Cap_Binary) %>%                # Group by Mkt_Cap: small vs large
    summarise(avg_return = mean(F_Return))      # Simple pivot table

It can be useful to see how often stocks switch from one family to another (from below median to above median or vice-versa). Below, we show a plot of Mkt_Cap, conditional on Mkt_Cap being above the current median.

data %>% group_by(Date) %>%                         # Group by date
    mutate(Mkt_Cap_median = median(Mkt_Cap)) %>%    # Compute median cap for each date
    filter(Mkt_Cap > Mkt_Cap_median) %>%            # Keep only the large stocks
    ggplot(aes(x = Date, y = Mkt_Cap, color = Tick)) + geom_line() + ylim(75000,250000) +
        geom_line(aes(x = Date, y = Mkt_Cap_median), color = "black") 

# The black line shows the running median

The straight lines show the discontinuities: one stock being large at some point in time, then small and then large again. The straight lines show the periods when the stock was small. The black line shows the median capitalisation (in the sample). Finally, because we focus in the zone close to the median and impose an upper limit of 250B$, there are some missing points.

5 Exercises

5.1 Rolling window

Change the main loop so that only 60 points of data are given to the weighting scheme(s). Sixty points amount to 5 years of monthly data.

5.2 Other performance metrics

Using the PerformanceAnalytics package (install it first), compute the maximum drawdown via: https://www.rdocumentation.org/packages/PerformanceAnalytics/versions/1.5.2/topics/maxDrawdown

Compute the transaction cost-adjusted SR: \(TC-SR=(\bar{r}-0.005*Turn)/\sigma\).

Add both metrics to the perf_met() function.

5.3 Minimum variance

Add the MV portfolio to the set of strategies. The weights depend only on the covariance matrix: \(w=\frac{\Sigma^{-1}1}{1'\Sigma^{-1}1}\).

5.4 map() expertise

Extend the map() syntax to the case with many strategies.

5.5 Realistic portfolios

In practice, many saveguards are applied, if only to reduce turnover. One such example is box constraint: the weights in the portfolio must not lie above or below user-specified thresholds.

Add a winsorising feature in the weights function that allows to cut the weights accordingly. If possible, add arguments directly to the function. Don’t forget to normalise the weights ex-post!

LS0tCnRpdGxlOiAiUG9ydGZvbGlvIGJhc2ljcyIKb3V0cHV0OiAKICBodG1sX25vdGVib29rOgogICAgdG9jOiB0cnVlCiAgICBudW1iZXJfc2VjdGlvbnM6IHRydWUKICAgIHRvY19mbG9hdDogCiAgICAgIGNvbGxhcHNlZDogZmFsc2UKLS0tCgpUaGlzIGlzIHRoZSBjb21wYW5pb24gbm90ZWJvb2sgdG8gdGhlIGludHJvZHVjdG9yeSBjb3Vyc2Ugb24gc2ltcGxlICoqcG9ydGZvbGlvIGNvbnN0cnVjdGlvbioqIGFuZCAqKnBlcmZvcm1hbmNlIG1ldHJpY3MqKi4gSXQgY29udGFpbnMgc2ltcGxlIGV4YW1wbGVzIG9mICoqcG9ydGZvbGlvIGJhY2t0ZXN0aW5nKiouIFRoZSBzdHJ1Y3R1cmVzIG9mIHRoaXMgc2VjdGlvbiB3aWxsIGJlIHVzZWQgbGF0ZXIgb24gaW4gdGhlIGNvdXJzZS4KCiRccmlnaHRhcnJvdyQgKipBQk9VVCBUSEUgTk9URUJPT0sqKjogICAKCi0gdGhlIGNvZGUgY2h1bmtzIGFyZSAqKnNlcXVlbnRpYWwqKi4gVGhleSBtdXN0IGJlIGV4ZWN1dGVkIGluIHRoZSBjb3JyZWN0IG9yZGVyLiAgCi0gdGV4dCBiZXR3ZWVuICoqc3RhcnMqKiBhcHBlYXJzIGluIGJvbGQgaW4gaHRtbCBmb3JtYXQuICAKCiMgQSBnbGltcHNlIGF0IHRoZSBTJlA1MDAKVGhlICoqUyZQNTAwKiogaXMgb25lIG9mIHRoZSBtb3N0IHdpZGVseSBzY3J1dGluaXNlZCBpbmRleCBpbiB0aGUgVVMgRXF1aXR5IGludmVzdG1lbnQgc3BhY2UuIEl0IHNlcnZlcyB2ZXJ5IG9mdGVuIGFzICoqYmVuY2htYXJrKiouIFRoZSBwdXJwb3NlIG9mIHRoaXMgc2VjdGlvbiBpcyB0byB1bnZlaWwgYSBmZXcgb2YgaXRzIHN0YXRpc3RpY2FsIHByb3BlcnRpZXMgYW5kIHRvIHVzZSB0aGUgKipoaWdoY2hhcnRlcioqIHBhY2thZ2UgZm9yIGhpZ2hjaGFydCByZW5kZXJpbmcgaW4gUi4KCiMjIFByaWNlcwpXZSBzdGFydCBieSBsb2FkaW5nIHRoZSBwYWNrYWdlcyBhbmQgZG93bmxvYWRpbmcgdGhlIGRhdGEuCgpgYGB7ciBsb2FkLCB3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRX0KaWYoIXJlcXVpcmUoaGlnaGNoYXJ0ZXIpKXtpbnN0YWxsLnBhY2thZ2VzKCJoaWdoY2hhcnRlciIpfSAjIFBhY2thZ2UgZm9yIG5pY2UgZmluYW5jaWFsIGdyYXBocwpsaWJyYXJ5KHRpZHl2ZXJzZSkKbGlicmFyeShsdWJyaWRhdGUpCmxpYnJhcnkocXVhbnRtb2QpICAgICMgVGhlIHBhY2thZ2UgdGhhdCBlYXNlcyB0aGUgZG93bmxvYWRpbmcgb2YgZmluYW5jaWFsIGRhdGEKbGlicmFyeShoaWdoY2hhcnRlcikgIyBUaGUgcGFja2FnZSBmb3IgZmluYW5jaWFsIHRpbWUtc2VyaWVzIHBsb3RzCgptaW5fZGF0ZSA8LSAiMTk5NS0wMS0wMSIKbWF4X2RhdGUgPC0gIjIwMTktMDItMTIiCnByaWNlcyA8LSBnZXRTeW1ib2xzKCJeR1NQQyIsIHNyYyA9ICd5YWhvbycsICAjIFlhaG9vIHNvdXJjZSAoc3RyYW5nZSB0aWNrZXIpCiAgICAgICAgICAgICBmcm9tID0gbWluX2RhdGUsIAogICAgICAgICAgICAgdG8gPSBtYXhfZGF0ZSwKICAgICAgICAgICAgIGF1dG8uYXNzaWduID0gVFJVRSwgCiAgICAgICAgICAgICB3YXJuaW5ncyA9IEZBTFNFKSAlPiUgCiAgbWFwKH5BZChnZXQoLikpKSAlPiUgCiAgcmVkdWNlKG1lcmdlKSAlPiUKICBgY29sbmFtZXM8LWAoIlNQNTAwIikKYGBgCgoKVGhlbiwgd2UgdHVybiB0byBwbG90dGluZywgdXNpbmcgKipoaWdoY2hhcnQqKiBmb3JtYXQuIFdlIHVuZGVybGluZSB0aGF0IHRoaXMgcGFja2FnZSB3b3JrcyB3aXRoIHNwZWNpYWwgKip4dHMqKiAoUiBleHRlbnNpYmxlIHRpbWUtc2VyaWVzKSBmb3JtYXQuIFdlIHBvaW50IHRvIHRoZSBwYWNrYWdlIHJlZmVyZW5jZSBmb3IgbW9yZSBkZXRhaWxzIG9uIHRoaXMgc3ViamVjdC4KCmBgYHtyIGhpZ2hjaGFydH0KaGMgPC0gaGlnaGNoYXJ0KHR5cGUgPSAic3RvY2siKSAlPiUKICAgIGhjX3RpdGxlKHRleHQgPSAiRXZvbHV0aW9uIG9mIHRoZSBTJlA1MDAiKSAlPiUKICAgIGhjX2FkZF9zZXJpZXMocHJpY2VzKQpodG1sdG9vbHM6OnRhZ0xpc3QoaGMpICAgICAgICAgICAgICAjIFVzZWQgZm9yIGh0bWwgZXhwb3J0CmV4cG9ydF9oYyhoYywgZmlsZW5hbWUgPSAiaGMuanMiKSAgICMgRXhwb3J0CmBgYAoKPHNjcmlwdCB0eXBlPSJ0ZXh0L2phdmFzY3JpcHQiIHNyYz0iaGMuanMiPjwvc2NyaXB0PgoKQSBuaWNlIGZlYXR1cmUgb2YgaGlnaGNoYXJ0cyBpcyB0aGF0IHRoZXkgYWxsb3cgdGhlIHVzZXIgdG8gY2hhbmdlIHRoZSBvYnNlcnZhdGlvbiBwZXJpb2QgYW5kIHNlZSB0aGUgdmFsdWVzIG9mIHBvaW50cyBvbiB0aGUgY3VydmUuIAoKIyMgUmV0dXJucwpOZXh0LCB3ZSB0dXJuIHRvIHRoZSBkaXN0cmlidXRpb24gb2YgcmV0dXJucy4KCmBgYHtyfQpyZXR1cm5zIDwtIChwcmljZXMvbGFnKHByaWNlcykgLSAxKSAlPiUgIyBGb3JtdWxhIGZvciByZXR1cm5zCiAgICBkYXRhLmZyYW1lKERhdGUgPSBpbmRleCguKSkgICAgICU+JSAjIEFkZGluZyB0aGUgRGF0ZSBhcyBhIGNvbHVtbgogICAgbmEub21pdCgpICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBSZW1vdmluZyBOQSByb3dzCm0gPC0gbWVhbihyZXR1cm5zJFNQNTAwKSAgICAgICAgICAgICAgICAjIEF2ZXJhZ2UgZGFpbHkgcmV0dXJuCnMgPC0gc2QocmV0dXJucyRTUDUwMCkgICAgICAgICAgICAgICAgICAjIFZvbGF0aWxpdHkgPSBzZCBvZiBkYWlseSByZXR1cm5zCgpyZXR1cm5zICU+JSBnZ3Bsb3QoKSArICAgICAgICAgICAgICAgICAgIyBQbG90CiAgICBnZW9tX2hpc3RvZ3JhbShhZXMoeCA9IFNQNTAwLCB5ID0gLi5kZW5zaXR5Li4pLCBiaW5zID0gMTAwKSArCiAgICBzdGF0X2Z1bmN0aW9uKGZ1biA9IGRub3JtLCBhcmdzID0gbGlzdChtZWFuID0gbSwgc2QgPSBzKSwgYWVzKGNvbG9yID0gIkdhdXNzaWFuIikpCmBgYAoKV2UgcGxvdCB0aGUgR2F1c3NpYW4gZGlzdHJpYnV0aW9uIHdpdGggcGFyYW1ldGVycyBjb3JyZXNwb25kaW5nIHRvIHRoZSBzYW1wbGUgbWVhbiBhbmQgc3RhbmRhcmQgZGV2aWF0aW9uLiBTbWFsbCBncmV5IHJlY3RhbmdsZXMgYXJvdW5kICRccG0gMC4wNSQgaW5kaWNhdGUgdGhhdCBsYXJnZSBwb3NpdGl2ZSBhbmQgbmVnYXRpdmUgcmV0dXJucyBvY2N1ciBtb3JlIG9mdGVuIHRoYW4gZXN0aW1hdGUgYnkgdGhlIEdhdXNzaWFuIGxhdzogdGhlIHRhaWxzIG9mIHRoZWlyIGRpc3RyaWJ1dGlvbiBhcmUgbm90b3Jpb3VzbHkgKipoZWF2eSoqLgoKIyMgVm9sYXRpbGl0eQpGaW5hbGx5LCB3ZSB0YWtlIGEgZHluYW1pYyBsb29rIGF0IHRoZSB2b2xhdGlsaXR5LiBXZSB0YWtlIGEgZnJ1Z2FsIGFwcHJvYWNoOyBtdWNoIG1vcmUgZWxlZ2FudCBtZXRob2RzIGFyZSBwcmVzZW50ZWQgaW4gU2VjdGlvbiA0LjUgb2YgKipSZXByb2R1Y2libGUgRmluYW5jZSoqIGJ5IEpvbmF0aGFuIFJlZ2Vuc3RlaW4uCgpgYGB7ciB2b2x9Cm5iX2RheXMgPC0gNjMgICAjIDYzIGRheXMgcm91Z2hseSBlcXVpdmFsZW50IHRvIDMgbW9udGhzIAp2b2wgPC0gMCAgICAgICAgIyBJbml0aWFsaXNhdGlvbgpmb3IoaSBpbiAxOihucm93KHJldHVybnMpIC0gbmJfZGF5cyArIDEpKXsgICAgICAgICAgIyBMb29wIG9uIGRhdGVzOiBub3QgZWxlZ2FudCEKICB2b2xbaV0gPC0gc2QocmV0dXJucyRTUDUwMFtpOihpICsgbmJfZGF5cyAtIDEpXSkgICMgVm9sIGNvbXB1dGVkIG9uIHJvbGxpbmcgd2luZG93IG9mIG5iX2RheXMKfQpEYXRlIDwtIHJldHVybnMkRGF0ZVtuYl9kYXlzOm5yb3cocmV0dXJucyldCnZvbCA8LSBkYXRhLmZyYW1lKHZvbCpzcXJ0KDI1MikpCgpyb3duYW1lcyh2b2wpIDwtIERhdGUKaGNfdm9sIDwtIGhpZ2hjaGFydCh0eXBlID0gInN0b2NrIikgJT4lCiAgICBoY190aXRsZSh0ZXh0ID0gIkV2b2x1dGlvbiBvZiB2b2xhdGlsaXR5IikgJT4lCiAgICBoY19hZGRfc2VyaWVzKGFzLnh0cyh2b2wpKQpodG1sdG9vbHM6OnRhZ0xpc3QoaGNfdm9sKSAgICAgICAgICAgICAgIyBVc2VkIGZvciBodG1sIGV4cG9ydApgYGAKCkNsZWFybHkgdGhlIGdyYXBoIHNob3dzIHBlcmlvZHMgb2YgbG93IHZvbGF0aWxpdHkgYW5kICoqY2x1c3RlcnMqKiBvZiBoaWdoIG1hcmtldCB0dXJidWxlbmNlIChjcmFzaGVzLCBtb3N0IG9mIHRoZSB0aW1lKS4gUmV0dXJucyBhcmUgdGhlcmVmb3JlICoqbm90IHN0YXRpb25hcnkqKi4gVGhlIHByb3BlcnRpZXMgd2UgZXhoaWJpdGVkIGZvciB0aGUgUyZQNTAwIGFyZSBhbHNvIHRydWUgYXQgdGhlIGluZGl2aWR1YWwgc3RvY2sgbGV2ZWwuCgpJbiB0aGUgbmV4dCBzZWN0aW9uLCB3ZSB0dXJuIHRvIHRoZSBjb3JlIHRvcGljIG9mICoqcG9ydGZvbGlvIGJhY2t0ZXN0aW5nKiouCgoKIyBBIHVuaXZlcnNlIG9mIGZ1bmN0aW9ucwoKQmFja3Rlc3RpbmcgcG9ydGZvbGlvIHN0cmF0ZWdpZXMgaXMgdXN1YWxseSBzaW1wbGUgYXQgZmlyc3QsIGJ1dCBiZWNvbWVzIG1vcmUgaW50cmljYXRlIHdoZW4gbWFueSBvcHRpb25zIGFyZSBjb25zaWRlcmVkLiBUbyBrZWVwIHRoaW5ncyBzaW1wbGUsIGl0IGlzIG1vcmUgZWZmaWNpZW50IHRvIHdvcmsgd2l0aCBmdW5jdGlvbnMuICoqRnVuY3Rpb25zIGhlbHAgY29tcGFydG1lbnRhbGlzZSB0aGUgZGlmZmVyZW50IHRhc2tzIG9mIHRoZSBwcm9jZXNzKiouIFdlIHdpbGwgYnVpbGQgZnVuY3Rpb25zIHRoYXQgY29tcHV0ZSBwb3J0Zm9saW8gd2VpZ2h0cyBhbmQgb3RoZXJzIHRoYXQgZXZhbHVhdGUgdGhlIHBlcmZvcm1hbmNlIG1ldHJpY3Mgb2YgdGhlIHN0cmF0ZWdpZXMuIFdoaWxlIHdlIHdpbGwgdXN1YWxseSB3b3JrIHdpdGggYSBsb29wIG9uIGJhY2t0ZXN0aW5nIGRhdGVzLCBpdCBpcyBwb3NzaWJsZSB0byBidWlsZCBmdW5jdGlvbnMgdGhhdCBkaXJlY3RseSBnZW5lcmF0ZSBwb3J0Zm9saW8gcmV0dXJucyAoc2VlIGJlbG93OiB0aGUgbWFwKCkgZnVuY3Rpb24pLgoKQnV0IGZpcnN0LCB3ZSBzdGFydCB3aXRoIHRoZSBwcmVwcm9jZXNzaW5nIG9mIHRoZSBkYXRhLgoKIyMgRGF0YSBwcmVwYXJhdGlvbgpXZSBmaXJzdCBpbXBvcnQgYW5kIGFycmFuZ2UgdGhlIGRhdGEuIApUaGUgZGF0YSBjb25zaXN0cyBvZiBtb25odGx5IGZpbmFuY2lhbCBpbmZvcm1hdGlvbiBwZXJ0YWluaW5nIHRvIDMwIGxhcmdlIFVTIGZpcm1zLiBUaGV5IGFyZSBjaGFyYWN0ZXJpc2VkIGJ5IHRoZWlyICoqdGlja2VyKiogc3ltYm9sOiAgCgp8QSAtIEZ8IEcgLSBNIHxPIC0gWnwKfCAtLS0gfCAtLS0tLSB8IC0tLSB8CnwgQUFQTCAoQXBwbGUpfCBHRSAoR2VuZXJhbCBFbGVjdHJpYykgfCBPUkNMIChPcmFjbGUpCnwgQkEgKEJvZWluZykgfCBIRCAoSG9tZSBEZXBvdCkgfCBQRkUgKFBmaXplcikKfCBCQUMgKEJhbmsgb2YgQW1lcmljYSkgfCBJQk0gfCBQRyAoUHJvY3RlciAmIEdhbWJsZSkKfCBDIChDaXRpZ3JvdXApIHwgSU5UQyAoSW50ZWwpIHwgVCAoQVQmVCkKfENTQ08gKENpc2NvKSB8IEpOSiAoSm9obnNvbiAmIEpvaG5zb24pIHwgIFVOSCAoVW5pdGVkIEhlYWx0aCkKfENWUyAoQ1ZTIEhlYWx0aCkgfCBKUE0gKEpQIE1vcmdhbikgfCBVUFMgCnxDVlggKENoZXZyb24pIHwgSyAoS2VsbG9nZykgfCBWWiAoVmVyaXpvbikKfEQgKERvbWluaW9uIEVuZXJneSkgfCBNQ0sgKE1jS2Vzc29uKSB8IFdGQyAoV2VsbHMgRmFyZ28pCnxESVMgKERpc25leSkgfCBNUksgKE1lcmNrKSB8IFdNVCAoV2FsbWFydCkKfEYgKEZvcmQpIHwgTVNGVCAoTWljcm9zb2Z0KSB8IFhPTSAoRXh4b24pCgoKVGhlcmUgYXJlIDcgYXR0cmlidXRlczogY2xvc2luZyBwcmljZSAoKipDbG9zZSoqKSwgbWFya2V0IGNhcGl0YWxpc2F0aW9uIGluIE0kICgqKk1rdF9DYXAqKiksIHByaWNlLXRvLWJvb2sgcmF0aW8gKCoqUDJCKiopLCAxIG1vbnRoIHZvbGF0aWxpdHkgKCoqVm9sXzFNKiopLCAxIG1vbnRoIHJlbGF0aXZlIHN0cmVuZ3RoIGluZGV4ICgqKlJTSV8xTSoqKSwgZGVidC10by1lcXVpdHkgcmF0aW8gKCoqRDJFKiopIGFuZCBwcm9maXRhYmlsaXR5IG1hcmdpbiAoKipQcm9mX01hcmcqKikuICAgCkZpbmFsbHksIHRoZSB0aW1lIHJhbmdlIGlzIDIwMDAtMjAxOC4KCmBgYHtyIGluaXRpYXRlLCB3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRX0KbG9hZCgiZGF0YS5SRGF0YSIpICAgICAgICAgICAgICAgICAgICAgICMgTG9hZGluZyB0aGUgZGF0YTogSUYgRElSRUNUT1JZIE9LIQpkYXRhIDwtIGRhdGEgJT4lIGFycmFuZ2UoRGF0ZSxUaWNrKSAgICAgIyBSYW5rZWQgZmlyc3QgYWNjb3JkaW5nIHRvIGRhdGUgYW5kIHRoZW4gc3RvY2tzCnN1bW1hcnkoZGF0YSkgICAgICAgICAgICAgICAgICAgICAgICAgICAjIERlc2NyaXB0aXZlIHN0YXRpc3RpY3MKYGBgCgpUaGlzIHNpbXBsZSB0YWJsZSBzaG93cyBhIHBvc3NpYmxlIG91dGxpZXIgZm9yIHRoZSAqKlAyQioqIHZhcmlhYmxlLiBUaGUgbWF4aW11bSB2YWx1ZSBpcyBjbGVhcmx5IG91dCBvZiByYW5nZS4gIApOZXh0LCB3ZSBmb3JtYXQgdGhlIGRhdGEgZm9yIGZ1dHVyZSB1c2UuIE5vdGFibHksIHdlIGNvbXB1dGUgcmV0dXJucy4KCmBgYHtyIGZvcm1hdCwgd2FybmluZyA9IEZBTFNFfQpkYXRhIDwtIGRhdGEgICU+JSAKICAgIGdyb3VwX2J5KFRpY2spICU+JSAgICAgICAgICAgICAgICAgICAgICAgICAgIyBHcm91cGluZzogcmV0dXJucyBjb21wdXRlZCBzdG9jay1ieS1zdG9jawogICAgbXV0YXRlKFJldHVybiA9IENsb3NlIC8gbGFnKENsb3NlKSAtIDEpICU+JSAjIEFkZGluZyByZXR1cm5zCiAgICBuYS5vbWl0KCkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgVGFrZSBvdXQgbWlzc2luZyB2YWx1ZXMKCnJldHVybnMgPC0gZGF0YSAlPiUgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgVGFrZSBkYXRhCiAgICBzZWxlY3QoVGljaywgRGF0ZSwgUmV0dXJuKSAlPiUgICAgICAgICAgICAgICMgU2VsZWN0IDMgY29sdW1ucwogICAgc3ByZWFkKGtleSA9IFRpY2ssIHZhbHVlID0gUmV0dXJuKSAgICAgICAgICAjIFB1dCB0aGVtIGludG8gJ21hdHJpeCcgZm9ybWF0CnJldHVybnMgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgU2hvdyB0aGUgcmV0dXJucwpgYGAKCkJ5IGRlZmluaXRpb24sIGEgcG9ydGZvbGlvIGlzIGEgY2hvaWNlIG9mIHdlaWdodHMgdGhhdCBzdW0gdG8gb25lLiBCZWxvdywgd2UgaW1wbGVtZW50IHR3byBjbGFzc2ljYWwgd2VpZ2h0aW5nIHNjaGVtZXM6IHRoZSB1bmlmb3JtIHBvcnRmb2xpbyAoKipFVyoqID0gZXF1YWwgd2VpZ2h0cykgYW5kIHRoZSBtYXhpbXVtIFNoYXJwZSByYXRpbyBwb3J0Zm9saW8gKCoqTVNSKiopLiBUaGUgbGF0dGVyIGlzIG1vcmUgY29tcGxpY2F0ZWQgYW5kIHJlcXVpcmVzIGlucHV0czogbmFtZWx5IHRoZSBjb2x1bW4gdmVjdG9yIG9mIChleHBlY3RlZCkgbWVhbiAkXG11JCBhbmQgY292YXJpYW5jZSBtYXRyaXggJFxTaWdtYSQgb2YgdGhlIGFzc2V0cy4gRm9yIHNpbXBsaWNpdHksIHdlIHdpbGwgZXN0aW1hdGUgdGhlbSB1c2luZyAqKnNhbXBsZSBtb21lbnRzKiogLSBldmVuIHRob3VnaCB0aGlzIGlzIGtub3duIHRvIGJlIGEgYmFkIGNob2ljZS4gVGhpcyByZXF1aXJlcyBhbiBhZGRpdGlvbmFsIGFyZ3VtZW50IGluIHRoZSBmdW5jdGlvbjogdGhlIGFzc2V0cycgcGFzdCByZXR1cm5zLiBUaGUgKipNU1IqKiB3ZWlnaHRzIGFyZSAkdz1cZnJhY3tcU2lnbWFeey0xfVxtdX17MSdcU2lnbWFeey0xfVxtdX0kLiBCb3RoICRcbXUkIGFuZCAxIGFyZSB2ZWN0b3JzIGhlcmUuCgpgYGB7ciB3ZWlnaHRzfQp3ZWlnaHRzX21zciA8LSBmdW5jdGlvbihyZXR1cm5zKXsgIyByZXR1cm5zIHdpbGwgcmVmZXIgdG8gUEFTVCByZXR1cm5zCiAgICBtIDwtIGFwcGx5KHJldHVybnMsIDIsIG1lYW4pICAjIFZlY3RvciBvZiBhdmVyYWdlIHJldHVybnMKICAgIHNpZ21hIDwtIGNvdihyZXR1cm5zKSAgICAgICAgICMgQ292YXJpYW5jZSBtYXRyaXgKICAgIHcgPC0gc29sdmUoc2lnbWEpICUqJSBtICAgICAgICMgUmF3IHdlaWdodHMKICAgIHJldHVybih3IC8gc3VtKHcpKSAgICAgICAgICAgICMgUmV0dXJucyBub3JtYWxpc2VkIHdlaWdodHMKfQoKd2VpZ2h0c19ldyA8LSBmdW5jdGlvbihyZXR1cm5zKXsgICMgV2Uga2VlcCB0aGUgc2FtZSBzeW50YXggZm9yIHNpbXBsaWNpdHkKICAgIE4gPC0gbGVuZ3RoKHJldHVybnNbMSxdKSAgICAgICMgTnVtYmVyIG9mIGFzc2V0cwogICAgcmV0dXJuKHJlcCgxL04sTikpICAgICAgICAgICAgIyBXZWlnaHQgPSAxL04KfQpgYGAKCgpXZSBhcmUgbm93IHJlYWR5IHRvIHByb2NlZWQgd2l0aCB0aGUgKippbml0aWFsaXNhdGlvbioqIG9mIHRoZSB2YXJpYWJsZXMgdGhhdCB3aWxsIHVzZSBpbiB0aGUgbWFpbiBsb29wLgoKYGBge3IgaW5pdF8yLCB3YXJuaW5nID0gRkFMU0V9CnRpY2sgPC0gbGV2ZWxzKGRhdGEkVGljaykgICAgICAgICAgICAgICAjIFNldCBvZiBhc3NldHMKdF9hbGwgPC0gdW5pcXVlKGRhdGEkRGF0ZSkgICAgICAgICAgICAgICMgU2V0IG9mIGRhdGVzCnNlcF9kYXRlIDwtIGFzLkRhdGUoIjIwMTAtMDEtMDEiKSAgICAgICAjIFRoaXMgZGF0ZSBzZXBhcmF0ZXMgaW4tc2FtcGxlIHZzIG91dC1vZi1zYW1wbGUKdF9vb3MgPC0gdF9hbGxbdF9hbGwgPiBzZXBfZGF0ZV0gICAgICAgICMgT3V0LW9mLXNhbXBsZSBkYXRlcyAoaS5lLiwgdGVzdGluZyBzZXQpCnBvcnRmX3dlaWdodHMgPC0gbWF0cml4KDAsIG5yb3cgPSBsZW5ndGgodF9vb3MpLCAjIFdpbGwgc3RvcmUgcG9ydGZvbGlvIHdlaWdodHMKICAgICAgICAgICAgICAgICAgICAgICAgICAgbmNvbCA9IGxlbmd0aCh0aWNrKSkgCnBvcnRmX3JldHVybnMgPC0gYygpICAgICAgICAgICAgICAgICAgICAjIFdpbGwgc3RvcmUgcG9ydGZvbGlvIHJldHVybnMKYGBgCgojIyBBIGZpcnN0IGV4YW1wbGUKQXQgbGFzdCwgd2UgY2FuIHByb2NlZWQgdG8gdGhlIG1haW4gbG9vcC4gQSBub3RlIG9mIGNhdXRpb246IGJvdGggaW4gdGhlIHdlaWdodGluZyBzY2hlbWUgZnVuY3Rpb25zIGFuZCBpbiB0aGUgbG9vcCBiZWxvdywgd2UgYXNzdW1lIHdlbGwgZGVmaW5lZCAoZmluaXRlLCBpLmUuLCBub24gTkEpIGRhdGEuIE9idmlvdXNseSwgZmVlZGluZyAqKk5BKiogZGF0YSBpbiB0aGUgc3lzdGVtIHdpbGwgcHJvZHVjZSAqKk5BKiogb3V0cHV0cy4gVGhlcmUgYXJlIG9ubHkgZm91ciBzdGVwcyBpbiB0aGUgbG9vcDogIAoKMS4gZXh0cmFjdCB0aGUgZGF0YSAgCjIuIGNvbXB1dGUgcG9ydGZvbGlvIHdlaWdodHMgIAozLiBjb21wdXRlIHJlYWxpc2VkIHJldHVybnMgIAo0LiBkZXJpdmUgdGhlIHJldHVybiBvZiB0aGUgcG9ydGZvbGlvCgpgYGB7ciBtYWlufQpmb3IodCBpbiAxOmxlbmd0aCh0X29vcykpewogICAgdGVtcF9kYXRhIDwtIHJldHVybnMgJT4lIGZpbHRlcihEYXRlIDwgdF9vb3NbdF0pICMgMSkgRXh0cmFjdGluZyBwYXN0IGRhdGE6IGV4cGFuZGluZyB3aW5kb3chIAogICAgcG9ydGZfd2VpZ2h0c1t0LF0gPC0gdGVtcF9kYXRhICU+JSAgICAgICAgICAgICAgICMgMikgVGFrZSB0aGlzIHBhc3QgZGF0YSAKICAgICAgICBzZWxlY3QoLURhdGUpICU+JSAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIFRha2Ugb3V0IHRoZSBkYXRlIGNvbHVtbgogICAgICAgIHdlaWdodHNfbXNyKCkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgQXBwcGx5IHRoZSB3ZWlnaHRpbmcgc2NoZW1lIGZ1bmN0aW9uCiAgICByZWFsaXNlZF9yZXR1cm5zIDwtIHJldHVybnMgJT4lICAgICAgICAgICAgICAgICAgIyAzKSBUYWtlIHJldHVybnMKICAgICAgICBmaWx0ZXIoRGF0ZSA9PSAgdF9vb3NbdF0pICU+JSAgICAgICAgICAgICAgICAjIEtlZXAgb25seSBjdXJyZW50IGRhdGUKICAgICAgICBzZWxlY3QoLURhdGUpICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIFRha2Ugb3V0IHRoZSBkYXRlIGNvbHVtbgogICAgcG9ydGZfcmV0dXJuc1t0XSA8LSBzdW0ocG9ydGZfd2VpZ2h0c1t0LF0gKiByZWFsaXNlZF9yZXR1cm5zKSAjIDQpIENvbXB1dGUgdGhlIHJldHVybgp9CmBgYAoKSW4gdGhlIGFib3ZlICoqYmFja3Rlc3QqKiwgdGhlIGFtb3VudCBvZiBkYXRhIGNvbnNpZGVyZWQgdG8gZm9ybSB0aGUgcG9ydGZvbGlvIGRlY2lzaW9uIGluY3JlYXNlcyB3aXRoIHRpbWUgKCoqZXhwYW5kaW5nIHdpbmRvdyoqKS4gSXQgaXMgZWFzeSB0byBmaXggdGhlIG51bWJlciBvZiBkYXRhIHBvaW50IGF0IGVhY2ggc3RlcCBhbmQgcHJvY2VlZCBvbiByb2xsaW5nIHdpbmRvd3MgKGV4ZXJjaXNlKS4gTGlrZXdpc2UsIHN3aXRjaGluZyBmcm9tICoqTVNSKiogdG8gKipFVyoqIGlzIGltbWVkaWF0ZSAoanVzdCBjaGFuZ2UgdGhlIHdlaWdodGluZyBmdW5jdGlvbikuICAKClRoZSBtYWluIG91dHB1dCBpcyB0aGUgdmVjdG9yIG9mIHBvcnRmb2xpbyByZXR1cm5zLiBXZSBjYW4gZWFzaWx5IHBsb3QgdGhlICoqZXZvbHV0aW9uKiogb2YgdGhlIHBvcnRmb2xpbyB0aHJvdWdoIHRpbWUuCgpgYGB7ciBwb3J0X3Bsb3QsIHdhcm5pbmcgPSBGQUxTRX0KcG9ydCA8LSBkYXRhLmZyYW1lKHRfb29zLCBjdW1wcm9kKDErcG9ydGZfcmV0dXJucykpICAgICAgICAgIyBQb3J0Zi4gdmFsdWVzIHZpYSBjdW11bGF0aXZlIHByb2R1Y3QKY29sbmFtZXMocG9ydCkgPC0gYygiRGF0ZSIsICJQb3J0Zm9saW8iKSAgICAgICAgICAgICAgICAgICAgIyBDaGFuZ2luZyBjb2x1bW4gbmFtZXMKcG9ydCAlPiUgZ2dwbG90KCkgKyBnZW9tX2xpbmUoYWVzKHggPSBEYXRlLCB5ID0gUG9ydGZvbGlvKSkgIyBQbG90CmBgYAoKCkJlbG93LCB3ZSBjcmVhdGUgYSBmdW5jdGlvbiB0aGF0IHRha2VzIGEgc2VyaWVzIG9mIHJldHVybnMgYXMgaW5wdXQgYW5kIHByb3ZpZGVzIGEgZmV3IHNpbXBsZSAqKnBlcmZvcm1hbmNlIG1ldHJpY3MqKi4KCmBgYHtyIHBlcmZfbWV0LCB3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRX0KcGVyZl9tZXQgPC0gZnVuY3Rpb24ocmV0dXJucyl7CiAgICBhdmdfcmV0IDwtIG1lYW4ocmV0dXJucywgbmEucm0gPSBUKSAgICAgICAgICAgICAgICAgICAgICMgQXJpdGhtZXRpYyBtZWFuIAogICAgdm9sIDwtIHNkKHJldHVybnMsIG5hLnJtID0gVCkgICAgICAgICAgICAgICAgICAgICAgICAgICAjIFZvbGF0aWxpdHkKICAgIFNoYXJwZV9yYXRpbyA8LSBhdmdfcmV0IC8gdm9sICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBTaGFycGUgcmF0aW8KICAgIFZhUl81IDwtIHF1YW50aWxlKHJldHVybnMsIDAuMDUpICAgICAgICAgICAgICAgICAgICAgICAgIyBWYWx1ZS1hdC1yaXNrCiAgICBtZXQgPC0gZGF0YS5mcmFtZShhdmdfcmV0LCB2b2wsIFNoYXJwZV9yYXRpbywgVmFSXzUpICAgICMgQWdncmVnYXRpb24gb2YgYWxsIG9mIHRoaXMKICAgIHJvd25hbWVzKG1ldCkgPC0gIm1ldHJpY3MiCiAgICByZXR1cm4obWV0KQp9CnBlcmZfbWV0KHBvcnRmX3JldHVybnMpICMgTGV0J3MgdGVzdCBvbiB0aGUgYWN0dWFsIHJldHVybnMKYGBgCgpOb3RlOiB0aGUgdmFsdWVzIGFyZSBub3QgYW5udWFsaXNlZC4gVGhlIGFubnVhbGlzYXRpb24gY2FuIGJlIGRpcmVjdGx5IGNvZGVkIGludG8gdGhlIGZ1bmN0aW9uLiBBIGhldXJpc3RpYyB3YXkgdG8gcHJvY2VlZCBpcyB0byBtdWx0aXBseSBhdmVyYWdlIHJldHVybnMgYnkgMTIgYW5kIHZvbGF0aWxpdGllcyBieSAkXHNxcnR7MTJ9JCAtIHRob3VnaCB0aGlzIG9taXRzIHRoZSBjb21wb3VuZGluZyBlZmZlY3QuIFRoZXNlIHNpbXBsaWZpY2F0aW9ucyBhcmUgb2sgaWYgdGhleSBhcmUgdXNlZCB0byBjb21wYXJlIHN0cmF0ZWdpZXMuIFRoZSBWYWx1ZSBhdCBSaXNrIGlzIG5vbnRoZWxlc3MgZGVwZW5kZW50IG9uIHRoZSByZXR1cm4gaG9yaXpvbiBhbmQgY2Fubm90IGJlIHByb3hpZWQgc28gc2ltcGx5LiAgIAoKQW4gaW1wb3J0YW50IGluZGljYXRvciBpcyB0aGUgKip0dXJub3ZlcioqIG9mIHRoZSBwb3J0Zm9saW86IGl0IGFzc2Vzc2VzIGFzc2V0IHJvdGF0aW9uIGFuZCB0aHVzIGltcGFjdHMgdHJhbnNhY3Rpb24gY29zdHMuIFNpbXBsZSB0dXJub3ZlciBjb21wdXRlcyBhdmVyYWdlIGFic29sdXRlIHZhcmlhdGlvbiBpbiBwb3J0Zm9saW8gd2VpZ2h0czogJFx0ZXh0e1R1cm59PVxmcmFjezF9e1R9XHN1bV97dD0yfV5UXHN1bV97bj0xfV5OfHdfdF5uLXdfe3QtMX1ebnwkLiBGdWxsIHR1cm5vdmVyIHRha2VzIGludG8gYWNjb3VudCB0aGUgdmFyaWF0aW9uIG9mIHRoZSB3ZWlnaHRzIGJldHdlZW4gcmViYWxhbmNpbmcgZGF0ZXM6ICRcdGV4dHtUdXJufT1cZnJhY3sxfXtUfVxzdW1fe3Q9Mn1eVFxzdW1fe249MX1eTnx3X3Rebi13X3t0LX1ebnwkLCB3aGVyZSAkdC0kIGlzIHRoZSB0aW1lIGp1c3QgYmVmb3JlIHRoZSByZWJhbGFuY2luZyBkYXRlLiAKCmBgYHtyIHR1cm5vdmVyLCB3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRX0KdHVybm92ZXJfc2ltcGxlIDwtIGZ1bmN0aW9uKHdlaWdodHMpewogICAgdHVybiA8LSAwCiAgICBmb3IodCBpbiAyOmxlbmd0aCh0X29vcykpewogICAgICAgICAgdHVybiA8LSB0dXJuICsgc3VtKGFicyh3ZWlnaHRzW3QsXSAtIHdlaWdodHNbdC0xLF0pKSAjIFZhcmlhdGlvbiBpbiB3ZWlnaHRzCiAgICB9CiAgICByZXR1cm4odHVybi8obGVuZ3RoKHRfb29zKS0xKSkgICMgQkVXQVJFOiBtb250aGx5IHZhbHVlIQp9CnR1cm5vdmVyX3NpbXBsZShwb3J0Zl93ZWlnaHRzKSAgICAgICMgU2ltcGxlIHR1cm5vdmVyIQpgYGAKCkJlbG93LCB3ZSBzd2l0Y2ggdG8gdGhlIGZ1bGwgZGVmaW5pdGlvbiBvZiB0aGUgKip0dXJub3ZlcioqLiBJbiB0aGlzIGNhc2UsIHRoZSB2YXJpYXRpb24gaW4gd2VpZ2h0cyBpcyBhZGp1c3RlZCBiZWNhdXNlIHRoZSB3ZWlnaHQgcHJpb3IgdG8gcmViYWxhbmNpbmcgaGF2ZSBkcmlmdGVkLgoKYGBge3IgdHVybm92ZXJfZnVsbCwgd2FybmluZyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0V9CnR1cm5vdmVyX2Z1bGwgPC0gZnVuY3Rpb24od2VpZ2h0cywgYXNzZXRfcmV0dXJucywgdF9vb3MpewogICAgdHVybiA8LSAwCiAgICBmb3IodCBpbiAyOmxlbmd0aCh0X29vcykpewogICAgICAgIHJlYWxpc2VkX3JldHVybnMgPC0gcmV0dXJucyAlPiUgZmlsdGVyKERhdGUgPT0gdF9vb3NbdF0pICU+JSBzZWxlY3QoLURhdGUpCiAgICAgICAgcHJpb3Jfd2VpZ2h0cyA8LSB3ZWlnaHRzW3QtMSxdICogKDEgKyByZWFsaXNlZF9yZXR1cm5zKSAjIEJlZm9yZSByZWJhbGFuY2luZwogICAgICAgIHR1cm4gPC0gdHVybiArIGFwcGx5KGFicyh3ZWlnaHRzW3QsXSAtIHByaW9yX3dlaWdodHMvc3VtKHByaW9yX3dlaWdodHMpKSwxLHN1bSkKICAgIH0KICAgIHJldHVybih0dXJuLyhsZW5ndGgodF9vb3MpLTEpKQp9CmFzc2V0X3JldHVybnMgPC0gcmV0dXJucyAlPiUgZmlsdGVyKERhdGUgPiBzZXBfZGF0ZSkgICAgIyBBc3NldCByZXR1cm5zIG92ZXIgdGhlIGV4cGVyaW1lbnQKdHVybm92ZXJfZnVsbChwb3J0Zl93ZWlnaHRzLCBhc3NldF9yZXR1cm5zLCB0X29vcykgICAgICAjIFJlYWwgdHVybm92ZXIKYGBgCgpOb3RlIHRoYXQgdGhlIHR1cm5vdmVyIGlzIGNvbXB1dGVkIGF0IHRoZSBtb250aGx5IGZyZXF1ZW5jeS4gVGhlIHNlY29uZCB2YWx1ZSBpcyBhbHdheXMgbW9yZSByZWFsaXN0aWM7IGluIHRoaXMgY2FzZSBpdCBpcyBzdWJzdGFudGlhbGx5IGhpZ2hlciBjb21wYXJlZCB0byB0aGUgc2ltcGxpZmllZCBwcm94eS4gRm9yIHRoZSBzYWtlIG9mIGNvbXBhY3RuZXNzLCB0aGUgdHVybm92ZXIgc2hvdWxkIGJlIGluY2x1ZGVkIGluIHRoZSAqKnBlcmZfbWV0KiooKSBmdW5jdGlvbi4KCgojIEV4dGVuc2lvbnMKIyMgQ29tcGFyaW5nIHN0cmF0ZWdpZXMKCkFuIGltcG9ydGFudCBnZW5lcmFsaXNhdGlvbiBvZiB0aGUgYWJvdmUgZnJhbWV3b3JrIGlzIHRvIGNvbnNpZGVyIG1vcmUgdGhhbiBvbmUgc3RyYXRlZ3kuIENvbXBhcmlzb25zIGFyZSBjb21tb25wbGFjZSBpbiB0aGUgYXNzZXQgbWFuYWdlbWVudCBpbmR1c3RyeTogb2J2aW91c2x5LCBwZW9wbGUgbG9vayBmb3IgdGhlICpiZXN0KiBzdHJhdGVneSAoYWNjb3JkaW5nIHRvIHBhcnRpY3VsYXIgZ29hbHMsIGJlbGllZnMsIGFuZCBwcmVmZXJlbmNlcykuIEJlbG93LCB3ZSBzaG93IGhvdyB0aGlzIGNhbiBiZSBoYW5kbGVkLiBXZSB3aWxsIGNvbXBhcmUgdGhlIHR3byBzdHJhdGVnaWVzIHRoYXQgd2UgbWVudGlvbm5lZCBhYm92ZS4KRmlyc3QsIHdlIG5lZWQgdG8gcmUtaW5pdGlhdGUgdGhlIHZhcmlhYmxlcyBiZWNhdXNlIHRoZWlyIGRpbWVuc2lvbiB3aWxsIGNoYW5nZSAoKipOT1RFKio6IGFuIGFsdGVybmF0aXZlIHJvdXRlIHdvdWxkIGJlIHRvIHdvcmsgd2l0aCBsaXN0cykuIAoKYGBge3IgbXVsdGlfaW5pdCwgd2FybmluZyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0V9ClR0IDwtIGxlbmd0aCh0X29vcykgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIE5iIG9mIGNvbXB1dGF0aW9uIGRhdGVzIAojIEF2b2lkIFQgYmVjYXVzZSBUID0gVFJVRSEKbmJfcG9ydCA8LSAyICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgTmIgb2YgcG9ydGZvbGlvcwpwb3J0Zl93ZWlnaHRzIDwtIGFycmF5KDAsIGRpbSA9IGMoVHQsIG5iX3BvcnQsIGxlbmd0aCh0aWNrKSkpICAgIyBTdG9yZSB3ZWlnaHRzCnBvcnRmX3JldHVybnMgPC0gbWF0cml4KDAsIG5yb3cgPSBUdCwgbmNvbCA9IG5iX3BvcnQpICAgICAgICAgICAjIFN0b3JlIHJldHVybnMKYGBgCgpTZWNvbmQsIHdlIGVtYmVkIGFsbCB3ZWlnaHRpbmcgc2NoZW1lcyBpbnRvIG9uZSBzaW5nbGUgZnVuY3Rpb24uCgpgYGB7ciBtdWx0aV93ZWlnaHRzfQp3ZWlnaHRzX211bHRpIDwtIGZ1bmN0aW9uKHJldHVybnMsail7ICAgIyBTdHJhdGVnaWVzIGFyZSBpbmRleGVkIGJ5IGoKICAgIGlmKGogPT0gMSl7ICMgaiA9IDEgPT4gTVNSCiAgICAgICAgcmV0dXJuKHdlaWdodHNfbXNyKHJldHVybnMpKQogICAgfQogICAgaWYoaiA9PSAyKXsgIyBqID0gMiA9PiBFVwogICAgICAgIE4gPC0gbGVuZ3RoKHJldHVybnNbMSxdKQogICAgICAgIHJldHVybihyZXAoMS9OLE4pKQogICAgfQp9CmBgYAoKV2UgZGVjaWRlZCB0byByZWNvZGUgdGhlICoqRVcqKiBzdHJhdGVneSwgYnV0IHdlIGNvdWxkIGhhdmUgdXNlZCB0aGUgKip3ZWlnaHRzX2V3KiooKSBmdW5jdGlvbiBpbnN0ZWFkLgpGaW5hbGx5LCB0aGUgbWFpbiBsb29wIGlzIG9ubHkgbWFyZ2luYWxseSBkaWZmZXJlbnQgZnJvbSB0aGUgc2luZ2xlIHN0cmF0ZWd5IGxvb3AuCgpgYGB7ciBtdWx0aV9sb29wLCB3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRX0KZm9yKHQgaW4gMTpsZW5ndGgodF9vb3MpKXsKICAgIHRlbXBfZGF0YSA8LSByZXR1cm5zICU+JSAKICAgICAgICBmaWx0ZXIoRGF0ZSA8IHRfb29zW3RdKSAlPiUgCiAgICAgICAgc2VsZWN0KC1EYXRlKQogICAgZm9yKGogaW4gMTpuYl9wb3J0KXsgICAgICAgICAgICAgICAgICAgICAgICAgICAjIFRoaXMgaXMgdGhlIG5vdmVsdHk6IHdlIGxvb3Agb24gdGhlIHN0cmF0ZWdpZXMgCiAgICAgICAgcG9ydGZfd2VpZ2h0c1t0LGosXSA8LSB3ZWlnaHRzX211bHRpKHRlbXBfZGF0YSwgaikgICMgVGhlIHdlaWdodHMnIGZ1bmN0aW9uIGlzIGluZGV4ZWQgYnkgagogICAgICAgIHJlYWxpc2VkX3JldHVybnMgPC0gcmV0dXJucyAlPiUgCiAgICAgICAgICAgIGZpbHRlcihEYXRlID09ICB0X29vc1t0XSkgJT4lIAogICAgICAgICAgICBzZWxlY3QoLURhdGUpCiAgICAgICAgcG9ydGZfcmV0dXJuc1t0LGpdIDwtIHN1bShwb3J0Zl93ZWlnaHRzW3QsaixdICogcmVhbGlzZWRfcmV0dXJucykKICAgIH0KfQphcHBseShwb3J0Zl9yZXR1cm5zLDIscGVyZl9tZXQpICU+JSAgICAgICAgICAgICAgICAgICAgICMgVGFraW5nIHBlcmYgbWV0cmljcwogICAgdW5saXN0KCkgJT4lICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgRmxhdHRlbmluZyB0aGUgbGlzdAogICAgbWF0cml4KG5yb3cgPSAyLCBieXJvdyA9IFQpICU+JSAgICAgICAgICAgICAgICAgICAgICMgT3JkZXJpbmcgdGhlbQogICAgYGNvbG5hbWVzPC1gKGMoImF2Z19yZXQiLCAidm9sIiwgIlNSIiwgIlZhUiIpKSAlPiUgICMgQWRkaW5nIGNvbHVtbiBuYW1lcwogICAgZGF0YS5mcmFtZSgpICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgQ29udmVydGluZyB0byBkYXRhZnJhbWUKYXBwbHkocG9ydGZfd2VpZ2h0cywgMiwgdHVybm92ZXJfc2ltcGxlKSAlPiUgdW5saXN0KCkKYGBgCgpXZSByZWNhbGwgdGhlIG9yZGVyIG9mIHN0cmF0ZWdpZXM6ICoqTVNSKiogZmlyc3QgKGxpbmUpIGFuZCAqKkVXKiogc2Vjb25kIChsaW5lKS4gIAoKQWdhaW4sIHR1cm5vdmVyIHNob3VsZCAoYW5kIHdpbGwpIGJlIGFkZGVkIHRvIHRoZSBwZXJmb3JtYW5jZSBtZXRyaWMgZnVuY3Rpb24uIFNpbmNlIHVuaWZvcm0gd2VpZ2h0cyBhcmUgY29uc3RhbnQsIHRoZWlyIHNpbXBsaWZpZWQgdHVybm92ZXIgaXMgemVyby4gSW4gcHJhY3RpY2UsIHRoYXQgaXMgbm90IHRoZSBjYXNlIGJlY2F1c2Ugd2VpZ2h0cyBldm9sdmUgYWNjb3JkaW5nIHRvIGFzc2V0IHJldHVybnMuIFRoZSBhZGp1c3RtZW50IHdvdWxkIGltcGx5IG9ubHkgYSBzbWFsbCB0dXJub3Zlci4KClRoZXJlIGlzIGEgd2VsbC1kb2N1bWVudGVkIHN1YnN0YW50aWFsIGRpZmZlcmVuY2UgYmV0d2VlbiB0aGUgdHdvIHdlaWd0aW5nIHNjaGVtZXMgaW4gdGVybXMgb2YgYXNzZXQgcm90YXRpb24uIFRoZSBNU1IgdGhhdCB3ZSBjb21wdXRlIGlzIGNsZWFybHkgbm90IGNvbXBldGl0aXZlOiBldmVuIGJlZm9yZSB0cmFuc2FjdGlvbiBjb3N0cywgaXRzIFNoYXJwZSByYXRpbyBpcyBzbWFsbGVyIHRoYW4gdGhhdCBvZiB0aGUgRVcgcG9ydGZvbGlvIChzZWUgRGVNaWd1ZWwgZXQgYWwuICgyMDA5KSBmb3IgZnVydGhlciBldmlkZW5jZSBvbiB0aGUgcm9idXN0bmVzcyBvZiB0aGUgRVcgcG9ydGZvbGlvKS4KCgojIyBNYWtlIGRvIHdpdGhvdXQgbG9vcHMKCkZpbmFsbHksIHdlIHNob3cgaG93IHRvICoqYnlwYXNzIHRoZSBsb29wKiogb3ZlciBkYXRlcy4gV2hpbGUgdGhpcyBpcyBub3QgdXNlZnVsIG9uIHNtYWxsIGRhdGFzZXRzLCBpdCBjYW4gc2F2ZSB0aW1lIG9uIGxhcmdlIGRhdGFiYXNlcyBiZWNhdXNlIGxvb3BzIGFyZSBub3RvcmlvdXNseSB0aW1lLWNvbnN1bWluZy4gQmVsb3csIHdlIHNob3cgaG93IHRvIHByb2NlZWQgd2l0aCB0aGUgKiptYXAqKigpIGZ1bmN0aW9uIGluIHRoZSBzaW1wbGUgY2FzZSB3aXRoIG9ubHkgb25lIHN0cmF0ZWd5LgoKYGBge3IgbWFwLCB3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRX0KIyBXZSBjcmVhdGUgYSBmdW5jdGlvbiB0aGF0IHdpbGwgY29tcHV0ZSByZXR1cm5zIGZvciBlYWNoIGRhdGU6CnBvcnRfbWFwIDwtIGZ1bmN0aW9uKHRfb29zLCByZXR1cm5zKXsgICAgICAgICAgICAgCiAgICB0ZW1wX2RhdGEgPC0gcmV0dXJucyAlPiUgZmlsdGVyKERhdGUgPCB0X29vcykgIyBTdGlsbCBleHBhbmRpbmcgd2luZG93Li4uCiAgICBwb3J0Zl93ZWlnaHRzIDwtIHRlbXBfZGF0YSAlPiUgCiAgICAgICAgc2VsZWN0KC1EYXRlKSAlPiUgCiAgICAgICAgd2VpZ2h0c19tc3IoKQogICAgcmVhbGlzZWRfcmV0dXJucyA8LSByZXR1cm5zICU+JSAKICAgICAgICBmaWx0ZXIoRGF0ZSA9PSAgdF9vb3MpICU+JSAKICAgICAgICBzZWxlY3QoLURhdGUpCiAgICByZXR1cm4oc3VtKHBvcnRmX3dlaWdodHMgKiByZWFsaXNlZF9yZXR1cm5zKSkKfQojIHRoZSBtYXAoKSBmdW5jdGlvbiBkb2VzIGl0IGFsbCEKcG9ydGZfcmV0dXJucyA8LSB0X29vcyAlPiUgICAgICAgICAgICAgICAgICAgICAgIyBUaGUgdmFyaWFibGUgb3ZlciB3aGljaCB3ZSBsb29wCiAgICBtYXAofnBvcnRfbWFwKC54LCByZXR1cm5zID0gcmV0dXJucykpICU+JSAgICMgSXMgc2VudCB0byB0aGUgbWFwKCkgZnVuY3Rpb24KICAgIHVubGlzdCgpICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBUaGUgb3V0cHV0IGlzIGZsYXR0ZW5lZApwZXJmX21ldChwb3J0Zl9yZXR1cm5zKSAgICAgICAgICAgICAgICAgICAgICAgICAjIENvbXB1dGUgdGhlIHBlcmYgbWV0cmljcwpgYGAKCgojIENoYXJhY3RlcmlzdGljcy1iYXNlZCBjaG9pY2UKSW4gdGhpcyBzZWN0aW9uLCB3ZSBzdGFydCB0aGUgY2hhcHRlciBvZiBzdHJhdGVnaWVzIGJhc2VkIG9uIGZpcm0gY2hhcmFjdGVyaXN0aWNzICgqKmZlYXR1cmVzKiopLiBBcyBhbiBpbGx1c3RyYXRpb24sIHdlIGNoZWNrIGEgd2VsbC1kb2N1bWVudGVkICh0aG91Z2ggc3RpbGwgY29udHJvdmVyc2lhbCkgKiphbm9tYWx5Kio6IHRoZSAqKnNpemUgZWZmZWN0KiouIFdlIGJ1aWxkIHR3byBwb3J0Zm9saW9zOiBpbiB0aGUgZmlyc3QgKCpyZXNwKi4gc2Vjb25kKSBvbmUsIHdlIGludmVzdCBpbiB0aGUgZmlybXMgdGhhdCBoYXZlIGEgYmVsb3cgKCpyZXNwKi4gYWJvdmUpIG1lZGlhbiBtYXJrZXQgY2FwaXRhbGlzYXRpb24uIFRoZSBmaXJzdCBwb3J0Zm9saW8gd2lsbCBiZSBhICdzbWFsbCcgcG9ydGZvbGlvIGFuZCB0aGUgc2Vjb25kIG9uZSBhICdsYXJnZScgb25lLiBTdG9ja3MgYXJlIGVxdWFsbHktd2VpZ2h0ZWQgaW5zaWRlIHRoZSBwb3J0Zm9saW9zLgoKRmlyc3QsIHdlIHByZXBhcmUgdGhlIHZhcmlhYmxlcyBhbmQgZGVmaW5lIHRoZSAqKndlaWdodCBmdW5jdGlvbioqLgoKYGBge3IgY2hhcnNfMSwgd2FybmluZ3MgPSBGQUxTRSwgbWVzc2FnZSA9IEZBTFNFfQpuYl9wb3J0IDwtIDIgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIE5iIG9mIHBvcnRmb2xpb3MKcG9ydGZfd2VpZ2h0cyA8LSBhcnJheSgwLCBkaW0gPSBjKFR0LTEsIG5iX3BvcnQsIGxlbmd0aCh0aWNrKSkpICAgIyBXaGVyZSB3ZSBzdG9yZSB3ZWlnaHRzCnBvcnRmX3JldHVybnMgPC0gbWF0cml4KDAsIG5yb3cgPSBUdC0xLCBuY29sID0gbmJfcG9ydCkgICAgICAgICAgICMgV2hlcmUgd2Ugc3RvcmUgcmV0dXJucwoKd2VpZ2h0c19jYXAgPC0gZnVuY3Rpb24oZGF0YSxqKXsgICAgCiMgTW9yZSBnZW5lcmFsIHRoYW4gYmVmb3JlOiB3ZSBmZWVkIGFsbCB0aGUgZGF0YSwgbm90IGp1c3QgcmV0dXJucwogICAgbSA8LSBtZWRpYW4oZGF0YSRNa3RfQ2FwKSAgICAgICAjIENvbXB1dGUgdGhlIG1lZGlhbiBtYXJrZXQgY2FwCiAgICBuIDwtIG5yb3coZGF0YSkgICAgICAgICAgICAgICAgICMgQ29tcHV0ZSB0aGUgbnVtYmVyIG9mIGFzc2V0cwogICAgaWYoaiA9PSAxKXtyZXR1cm4oKGRhdGEkTWt0X0NhcCA8IG0pL24qMil9ICMgU21hbGwgY2FwCiAgICBpZihqID09IDIpe3JldHVybigoZGF0YSRNa3RfQ2FwID4gbSkvbioyKX0gIyBMYXJnZSBjYXAKfQpgYGAKClRoZXJlIHdpbGwgb25seSBiZSBUdC0xIGRhdGVzIHNpbmNlIHdlIGxvc2Ugb25lIGJlY2F1c2Ugb2YgdGhlIGNvbXB1dGF0aW9uIG9mIGZ1dHVyZSByZXR1cm5zLiAgCgpTZWNvbmQsIHdlIGNhbiBsYXVuY2ggdGhlICoqYmFja3Rlc3RpbmcgbG9vcCoqLgoKYGBge3IgY2hhcnNfMiwgd2FybmluZ3MgPSBGQUxTRSwgbWVzc2FnZSA9IEZBTFNFfQpmb3IodCBpbiAyOmxlbmd0aCh0X29vcykpewogICAgdGVtcF9kYXRhIDwtIGRhdGEgJT4lIGZpbHRlcihEYXRlID09IHRfb29zW3QtMV0pICAgICAgICAjIFdlIGtlZXAgdGhlIGRhdGEgb2YgdGhlIHByZXZpb3VzIGRhdGUKICAgIGZvcihqIGluIDE6bmJfcG9ydCl7ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBXZSBsb29wIG9uIHRoZSBzdHJhdGVnaWVzIAogICAgICAgIHBvcnRmX3dlaWdodHNbdC0xLGosXSA8LSB3ZWlnaHRzX2NhcCh0ZW1wX2RhdGEsIGopICAjIFRoZSB3ZWlnaHRzJyBmdW5jdGlvbiBpcyBpbmRleGVkIGJ5IGoKICAgICAgICByZWFsaXNlZF9yZXR1cm5zIDwtIHJldHVybnMgJT4lIAogICAgICAgICAgICBmaWx0ZXIoRGF0ZSA9PSAgdF9vb3NbdF0pICU+JSAKICAgICAgICAgICAgc2VsZWN0KC1EYXRlKQogICAgICAgIHBvcnRmX3JldHVybnNbdC0xLGpdIDwtIHN1bShwb3J0Zl93ZWlnaHRzW3QtMSxqLF0gKiByZWFsaXNlZF9yZXR1cm5zKQogICAgfQp9CmBgYAoKVGhpcmQsIHdlIHByb2NlZWQgdG8gcGVyZm9ybWFuY2UgbWV0cmljcy4KCmBgYHtyIGNoYXJzXzMsIHdhcm5pbmdzID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRX0KYXBwbHkocG9ydGZfcmV0dXJucywyLHBlcmZfbWV0KSAlPiUgICAgICAgICAgICAgICAgICAgICAjIFRha2luZyBwZXJmIG1ldHJpY3MKICAgIHVubGlzdCgpICU+JSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIEZsYXR0ZW5pbmcgdGhlIGxpc3QKICAgIG1hdHJpeChucm93ID0gMiwgYnlyb3cgPSBUKSAlPiUgICAgICAgICAgICAgICAgICAgICAjIE9yZGVyaW5nIHRoZW0KICAgIGBjb2xuYW1lczwtYChjKCJhdmdfcmV0IiwgInZvbCIsICJTUiIsICJWYVIiKSkgJT4lICAjIEFkZGluZyBjb2x1bW4gbmFtZXMKICAgIGRhdGEuZnJhbWUoKSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIENvbnZlcnRpbmcgdG8gZGF0YWZyYW1lCmBgYAoKU21hbGwgZmlybXMgZG8gaW5kZWVkIGdlbmVyYXRlIGEgaGlnaGVyIGxldmVsIG9mIHBlcmZvcm1hbmNlISBJbiBvcmRlciB0byByZWFjaCB0aGlzIGNvbmNsdXNpb24gaW4gYSByaWdvdXJvdXMgZmFzaGlvbiwgd2Ugd291bGQgbmVlZCB0byBwZXJmb3JtIHRoZSBzYW1lIGFuYWx5c2lzIG9uIGF0IGxlYXN0IDEsMDAwIHN0b2NrcyAoaWRlYWxseSwgbW9yZSkgYW5kIG9uIDUgdG8gMTAgcG9ydGZvbGlvIHNvcnRzIChmcm9tIHZlcnkgc21hbGwgZmlybXMgdG8gdmVyeSBsYXJnZSBvbmVzKS4gQmVsb3csIHdlIGNoZWNrIHRoZSB3ZWlnaHRzIG9mIHRoZSBwb3J0Zm9saW8gb24gb25lIHBhcnRpY3VsYXIgZGF0ZS4KCmBgYHtyIGNoZWNrLCB3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRX0Kc21hbGwgPC0gcG9ydGZfd2VpZ2h0c1syLDEsXSAjIHQgPSAyLCBqID0gMSAodF9vb3NbMl0gPSAyMDEwLTAzLTAxLCBzbWFsbCBmaXJtcykKbGFyZ2UgPC0gcG9ydGZfd2VpZ2h0c1syLDIsXSAjIHQgPSAyLCBqID0gMiAodF9vb3NbMl0gPSAyMDEwLTAzLTAxLCBsYXJnZSBmaXJtcykKZGF0YS5mcmFtZShzbWFsbCwgbGFyZ2UsIHJvdy5uYW1lcyA9IHRpY2spCmBgYAoKSW5kZWVkLCBzb21lIHN0b2NrcyBoYXZlIHplcm8gd2VpZ2h0cyBhbmQgb3RoZXJzIDEvMTUuICAKCkZpbmFsbHksIGxldCdzIHNlZSBob3cgd2UgY291bGQgaGF2ZSBjb2RlZCB0aG9zZSBzdHJhdGVnaWVzIHVzaW5nIHRoZSAqKnRpZHl2ZXJzZSoqIChhbmQgYSBsb3Qgb2YgcGlwaW5nISkuCgpgYGB7ciBwaXZvdCEsIHdhcm5pbmcgPSBGQUxTRSwgbWVzc2FnZSA9IEZBTFNFfQpkYXRhICU+JSBmaWx0ZXIoRGF0ZSA+IHNlcF9kYXRlKSAlPiUgICAgICAgICAgICAjIEtlZXAgb25seSB0aGUgb3V0LW9mLXNhbXBsZSBiYWNrdGVzdGluZyBkYXRlcwogICAgZ3JvdXBfYnkoVGljaykgJT4lICAgICAgICAgICAgICAgICAgICAgICAgICAjIEdyb3VwIGJ5IHN0b2NrCiAgICBtdXRhdGUoRl9SZXR1cm4gPSBsZWFkKFJldHVybikpICU+JSAgICAgICAgICMgQ29tcHV0ZSBmb3J3YXJkIChpLmUuLCByZWFsaXNlZCkgcmV0dXJuCiAgICBuYS5vbWl0KCkgJT4lICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgVGFrZSBvdXQgTkFzCiAgICBncm91cF9ieShEYXRlKSAlPiUgICAgICAgICAgICAgICAgICAgICAgICAgICMgR3JvdXAgYnkgZGF0ZXMKICAgIG11dGF0ZShNa3RfQ2FwX0JpbmFyeSA9IE1rdF9DYXAgPCBtZWRpYW4oTWt0X0NhcCkpICU+JSAgIyBDb21wdXRlIG1lZGlhbiBjYXAgZm9yIGVhY2ggZGF0ZQogICAgZ3JvdXBfYnkoTWt0X0NhcF9CaW5hcnkpICU+JSAgICAgICAgICAgICAgICAjIEdyb3VwIGJ5IE1rdF9DYXA6IHNtYWxsIHZzIGxhcmdlCiAgICBzdW1tYXJpc2UoYXZnX3JldHVybiA9IG1lYW4oRl9SZXR1cm4pKSAgICAgICMgU2ltcGxlIHBpdm90IHRhYmxlCmBgYAoKCkl0IGNhbiBiZSB1c2VmdWwgdG8gc2VlIGhvdyBvZnRlbiBzdG9ja3Mgc3dpdGNoIGZyb20gb25lIGZhbWlseSB0byBhbm90aGVyIChmcm9tIGJlbG93IG1lZGlhbiB0byBhYm92ZSBtZWRpYW4gb3IgdmljZS12ZXJzYSkuIEJlbG93LCB3ZSBzaG93IGEgcGxvdCBvZiAqKk1rdF9DYXAqKiwgY29uZGl0aW9uYWwgb24gKipNa3RfQ2FwKiogYmVpbmcgYWJvdmUgdGhlIGN1cnJlbnQgbWVkaWFuLiAKCmBgYHtyIGNhcF9ncmFwaCwgd2FybmluZyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0V9CmRhdGEgJT4lIGdyb3VwX2J5KERhdGUpICU+JSAgICAgICAgICAgICAgICAgICAgICAgICAjIEdyb3VwIGJ5IGRhdGUKICAgIG11dGF0ZShNa3RfQ2FwX21lZGlhbiA9IG1lZGlhbihNa3RfQ2FwKSkgJT4lICAgICMgQ29tcHV0ZSBtZWRpYW4gY2FwIGZvciBlYWNoIGRhdGUKICAgIGZpbHRlcihNa3RfQ2FwID4gTWt0X0NhcF9tZWRpYW4pICU+JSAgICAgICAgICAgICMgS2VlcCBvbmx5IHRoZSBsYXJnZSBzdG9ja3MKICAgIGdncGxvdChhZXMoeCA9IERhdGUsIHkgPSBNa3RfQ2FwLCBjb2xvciA9IFRpY2spKSArIGdlb21fbGluZSgpICsgeWxpbSg3NTAwMCwyNTAwMDApICsKICAgICAgICBnZW9tX2xpbmUoYWVzKHggPSBEYXRlLCB5ID0gTWt0X0NhcF9tZWRpYW4pLCBjb2xvciA9ICJibGFjayIpIAojIFRoZSBibGFjayBsaW5lIHNob3dzIHRoZSBydW5uaW5nIG1lZGlhbgpgYGAKClRoZSBzdHJhaWdodCBsaW5lcyBzaG93IHRoZSAqKmRpc2NvbnRpbnVpdGllcyoqOiBvbmUgc3RvY2sgYmVpbmcgbGFyZ2UgYXQgc29tZSBwb2ludCBpbiB0aW1lLCB0aGVuIHNtYWxsIGFuZCB0aGVuIGxhcmdlIGFnYWluLiBUaGUgc3RyYWlnaHQgbGluZXMgc2hvdyB0aGUgcGVyaW9kcyB3aGVuIHRoZSBzdG9jayB3YXMgc21hbGwuIFRoZSBibGFjayBsaW5lIHNob3dzIHRoZSBtZWRpYW4gY2FwaXRhbGlzYXRpb24gKGluIHRoZSBzYW1wbGUpLiBGaW5hbGx5LCBiZWNhdXNlIHdlIGZvY3VzIGluIHRoZSB6b25lIGNsb3NlIHRvIHRoZSBtZWRpYW4gYW5kIGltcG9zZSBhbiB1cHBlciBsaW1pdCBvZiAyNTBCJCwgdGhlcmUgYXJlIHNvbWUgbWlzc2luZyBwb2ludHMuCgoKIyBFeGVyY2lzZXMKCiMjIFJvbGxpbmcgd2luZG93CgpDaGFuZ2UgdGhlIG1haW4gbG9vcCBzbyB0aGF0IG9ubHkgNjAgcG9pbnRzIG9mIGRhdGEgYXJlIGdpdmVuIHRvIHRoZSB3ZWlnaHRpbmcgc2NoZW1lKHMpLiBTaXh0eSBwb2ludHMgYW1vdW50IHRvIDUgeWVhcnMgb2YgbW9udGhseSBkYXRhLgoKCmBgYHtyIHlvdXIgdHVybiF9CgpgYGAKCgojIyBPdGhlciBwZXJmb3JtYW5jZSBtZXRyaWNzClVzaW5nIHRoZSBQZXJmb3JtYW5jZUFuYWx5dGljcyBwYWNrYWdlIChpbnN0YWxsIGl0IGZpcnN0KSwgY29tcHV0ZSB0aGUgbWF4aW11bSBkcmF3ZG93biB2aWE6Cmh0dHBzOi8vd3d3LnJkb2N1bWVudGF0aW9uLm9yZy9wYWNrYWdlcy9QZXJmb3JtYW5jZUFuYWx5dGljcy92ZXJzaW9ucy8xLjUuMi90b3BpY3MvbWF4RHJhd2Rvd24KCkNvbXB1dGUgdGhlIHRyYW5zYWN0aW9uIGNvc3QtYWRqdXN0ZWQgU1I6ICRUQy1TUj0oXGJhcntyfS0wLjAwNSpUdXJuKS9cc2lnbWEkLgoKQWRkIGJvdGggbWV0cmljcyB0byB0aGUgcGVyZl9tZXQoKSBmdW5jdGlvbi4KCiMjIE1pbmltdW0gdmFyaWFuY2UKQWRkIHRoZSBNViBwb3J0Zm9saW8gdG8gdGhlIHNldCBvZiBzdHJhdGVnaWVzLiBUaGUgd2VpZ2h0cyBkZXBlbmQgb25seSBvbiB0aGUgY292YXJpYW5jZSBtYXRyaXg6ICR3PVxmcmFje1xTaWdtYV57LTF9MX17MSdcU2lnbWFeey0xfTF9JC4KCiMjIG1hcCgpIGV4cGVydGlzZQpFeHRlbmQgdGhlIG1hcCgpIHN5bnRheCB0byB0aGUgY2FzZSB3aXRoIG1hbnkgc3RyYXRlZ2llcy4KCiMjIFJlYWxpc3RpYyBwb3J0Zm9saW9zCkluIHByYWN0aWNlLCBtYW55IHNhdmVndWFyZHMgYXJlIGFwcGxpZWQsIGlmIG9ubHkgdG8gcmVkdWNlIHR1cm5vdmVyLiBPbmUgc3VjaCBleGFtcGxlIGlzIGJveCBjb25zdHJhaW50OiB0aGUgd2VpZ2h0cyBpbiB0aGUgcG9ydGZvbGlvIG11c3Qgbm90IGxpZSBhYm92ZSBvciBiZWxvdyB1c2VyLXNwZWNpZmllZCB0aHJlc2hvbGRzLiAKCkFkZCBhIHdpbnNvcmlzaW5nIGZlYXR1cmUgaW4gdGhlIHdlaWdodHMgZnVuY3Rpb24gdGhhdCBhbGxvd3MgdG8gY3V0IHRoZSB3ZWlnaHRzIGFjY29yZGluZ2x5LiBJZiBwb3NzaWJsZSwgYWRkIGFyZ3VtZW50cyBkaXJlY3RseSB0byB0aGUgZnVuY3Rpb24uIERvbid0IGZvcmdldCB0byBub3JtYWxpc2UgdGhlIHdlaWdodHMgZXgtcG9zdCEKCg==